The present invention generally relates to methods and apparatuses for compressing halftone image data, and more particularly to a method and an apparatus for compressing halftone image data with a high data compression ratio using a circuit having a small scale regardless of a period of screen dots in the halftone.
Recently, with the development of office automation systems, photographic images are processed in addition to character images as document information. Normally, the document is described in two levels of tone, that is, black and white. On the other hand, a photographic image is described by a density of black pixels such as the halftone which is described by the tone reproduction method by density of each element. For this reason, the data quantity of the photographic image is considerably large when compared to the data quantity of the character image. The data quantity of the photographic image is ten-odd times to several tens of times the data quantity of the character image. Accordingly, in order to efficiently process the photographic image when storing or transmitting the document, it is essential to use an efficient data compression system so as to reduce the data quantity.
A known predictive coding may be used to compress the halftone image data. As shown in FIG.1, reference pixels indicated by circular marks are taken around an object pixel indicated by a black circular mark and reference pixels indicated by rectangular marks are also taken at locations separated by one period of the screen dots from the object pixel. In FIG.1, PH denotes the period of the screen dots taken along a horizontal direction and PV denotes the period of the screen dots taken along a vertical direction. Whether the object pixel is black or white is predicted from the black or white state of each of the reference pixels, and a prediction error is coded.
However, in the case of a facsimile machine or the like which reads the document on a scanner and compresses the image data, there are various kinds of halftones and the period of the screen dots is in most cases not known beforehand. For this reason, an adaptive predictive coding is conventionally employed by providing a plurality of predictors which use reference pixels in correspondence with periods of various screen dots, selecting one of the predictors which have a smallest number of prediction errors, and carrying out the coding using the selected predictor.
In other words, two predictors having mutually different screen dot periods are provided as shown in FIG.2, for example. A conventional data compression system shown in FIG.2 includes a line memory 1, predictors 2 and 3 having mutually different screen dot periods, exclusive-OR circuits 4 and 5, a multiplexer 6, a coder 7, counters 8 and 9, and a comparator 10 which are connected as shown.
An input halftone image signal is supplied to the line memory 1 and stored therein. This input halftone image signal is also supplied to the exclusive-OR circuits 4 and 5. The predictors 2 and 3 respectively predict the black or white state of the input halftone image signal which is read out from the line memory 1 for each pixel, and the exclusive-OR circuits 4 and 5 respectively obtain prediction errors of the predictors 2 and 3. The prediction errors are supplied to the multiplexer 6.
On the other hand, the counters 8 and 9 respectively count the number of prediction errors made by the predictors 2 and 3 during a predetermined interval of the input halftone image signal. The comparator 10 compares the numbers of prediction errors counted in the counters 8 and 9 and outputs a selection signal which indicates the counter which has the smaller count, that is, the predictor with the smaller number of prediction errors. The multiplexer 6 selectively passes the prediction error which originates from the predictor with the smaller number of prediction errors in response to the selection signal during a next predetermined interval of the input halftone image signal. The coder 7 codes the prediction error output from the multiplexer 6, and a coded signal is output via an output terminal 12.
For example, the above described adaptive predictive coding is proposed in Usubuchi et al., "Adaptive Predictive Coding for Newspaper Facsimile", Proceedings of the IEEE, Vol.68, No.7, July 1980.
However, according to the conventional data compression system for compressing halftone images, the predictors are designed by predicting the statistical nature of the halftone images. For this reason, although an effective data compression can be made when the screen dot period of the predictor used matches the screen dot period of the actual halftone image, there is a problem in that the efficiency of the data compression considerably deteriorates when the screen dot period of the predictor used does not match the screen dot period of the actual halftone image. Of course, the deterioration of the efficiency of the data compression caused by the unmatched screen dot periods of the predictor and the actual halftone image is improved to a certain extent by the use of the adaptive predictive coding. But on the other hand, in order to greatly improve the deterioration of the efficiency of the data compression, it is necessary to increase the number of predictors and the scale of the circuit consequently becomes large thereby introducing a different problem.
On the other hand, universal coding schemes have been proposed. However, the universal coding focuses only on one-dimensional strings and there is still room for improving the data compression ratio.